home *** CD-ROM | disk | FTP | other *** search
/ C/C++ Users Group Library 1996 July / C-C++ Users Group Library July 1996.iso / vol_400 / 410_01 / wlist / wlist.cc < prev    next >
Encoding:
C/C++ Source or Header  |  1995-12-30  |  21.7 KB  |  770 lines
  1. static char sccs_id[] = "@(#)wlist.cc    1.1 2/15/94 10:38:13";
  2. /*+++
  3.  
  4.   :  :    wlist.cc
  5.  
  6.     PURPOSE : wlist member functions
  7.  
  8.     DATE    : Sat Jan 29 19:15:47 EST 1994
  9.  
  10.     AUTHOR  : W. Hatch
  11.  
  12.     PROJECT : WEH Software
  13.             
  14.     COMPANY : Coleman Research Corporation
  15.           9891 Broken Land Parkway
  16.           Suite 200
  17.           Columbia, Maryland 21045
  18.           Phone (301)621-8600
  19.           FAX (410)7210
  20. ---*/ 
  21. /*
  22. ------------------------------------------------------------------------
  23.   MODIFICATIONS
  24. DATE    PROGRAMMER    DESCRIPTION
  25. ========================================================================
  26. 2-15-94 W. Hatch    added functions ExchangePrevious(),
  27.             ExchangeNext(), Maximum(), Minimum(), Sort(),
  28.             Reverse(), Copy(), SetCompareData()
  29. */
  30.  
  31. #include <stdio.h>
  32. #include <string.h>
  33. #include <wlist.h>
  34.  
  35. //--------------------------------------------------------------------
  36. // constructor
  37. //--------------------------------------------------------------------
  38. wlist::wlist(){
  39.     //------------------------------------------------------------
  40.     // set size to zero, node pointers to null
  41.     //------------------------------------------------------------
  42.     size=0;
  43.     first=(node *)0;
  44.     last =(node *)0;
  45.     current=(node *)0;
  46.     name=new char[10];
  47.     strcpy(name,"noname");
  48.     CompareData = 0;
  49.     PrintData = 0;
  50. }
  51. //--------------------------------------------------------------------
  52. // destructor
  53. //--------------------------------------------------------------------
  54. wlist::~wlist(){
  55.     DeleteAll();
  56.     delete [] name;
  57. }
  58. //--------------------------------------------------------------------
  59. // Size - return list size
  60. //--------------------------------------------------------------------
  61. int wlist::Size(){return size;}
  62.  
  63. //--------------------------------------------------------------------
  64. // Name - access and assign list name
  65. //--------------------------------------------------------------------
  66. char *wlist::Name(){return name;}
  67.  
  68. char *wlist::Name(char *s){
  69.     if(s != (char *)0)
  70.     {
  71.         delete [] name;
  72.         name = new char[strlen(s)+1];
  73.         s[0]='\0';
  74.         strcpy(name,s);
  75.     }
  76.     return name;
  77. }
  78.  
  79.  
  80.  
  81. //--------------------------------------------------------------------
  82. // PrependData - add node to top of list
  83. //--------------------------------------------------------------------
  84. void *wlist::PrependData(void *v){
  85.     //------------------------------------------------------------
  86.     // create new node containing the given data
  87.     //------------------------------------------------------------
  88.     node *n = new node;
  89.     n->NodeData(v);
  90.     if(Size()==0)
  91.     {
  92.         //----------------------------------------------------
  93.         // list empty, insert 1 node
  94.         //----------------------------------------------------
  95.         current=n;
  96.         first = n;
  97.         last = n;
  98.     }
  99.     else
  100.     {
  101.         //----------------------------------------------------
  102.         // list not empty, insert 1 node, reset node pointers
  103.         // to maintain doubly linked list connectivity
  104.         //----------------------------------------------------
  105.         node *ff = first;
  106.  
  107.         current=n;
  108.         first=n;
  109.  
  110.         ff->PreviousNode(n);
  111.         n->NextNode(ff);
  112.     }
  113.     //------------------------------------------------------------
  114.     // increment node count
  115.     //------------------------------------------------------------
  116.     ++size;
  117.     return v;
  118. }
  119. //--------------------------------------------------------------------
  120. // AppendData - add data to end of list
  121. //--------------------------------------------------------------------
  122. void *wlist::AppendData(void *v){
  123.     //------------------------------------------------------------
  124.     // create new node containing the given data
  125.     //------------------------------------------------------------
  126.     node *n = new node;
  127.     n->NodeData(v);
  128.     if(Size()==0)
  129.     {
  130.         //----------------------------------------------------
  131.         // list empty, insert 1 node
  132.         //----------------------------------------------------
  133.         current=n;
  134.         first = n;
  135.         last = n;
  136.     }
  137.     else
  138.     {
  139.         //----------------------------------------------------
  140.         // list not empty, insert 1 node, reset node pointers
  141.         // to maintain doubly linked list connectivity
  142.         //----------------------------------------------------
  143.         node *ll = last;
  144.         last=n;
  145.         current = n;
  146.         ll->NextNode(n);
  147.         n->PreviousNode(ll);
  148.     }
  149.     //------------------------------------------------------------
  150.     // increment node count
  151.     //------------------------------------------------------------
  152.     ++size;
  153.     return v;
  154. }
  155. //--------------------------------------------------------------------
  156. // CurrentData - access and assign current data
  157. //--------------------------------------------------------------------
  158. void *wlist::CurrentData(){
  159.     if(Size() > 0)
  160.         //----------------------------------------------------
  161.         // list not empty, return current node data
  162.         //----------------------------------------------------
  163.         return current->NodeData();
  164.     else
  165.         //----------------------------------------------------
  166.         // list empty, return null
  167.         //----------------------------------------------------
  168.         return (void *)0;
  169. }
  170. void *wlist::CurrentData(void *v){
  171.     if(Size() > 0)
  172.         //----------------------------------------------------
  173.         // list not empty, replace current node contents
  174.         //----------------------------------------------------
  175.         return current->NodeData(v);
  176.     else
  177.     {
  178.         //----------------------------------------------------
  179.         // list empty, append given data
  180.         //----------------------------------------------------
  181.         return AppendData(v);
  182.     }
  183. }
  184. //--------------------------------------------------------------------
  185. // FirstData - access and assign first data
  186. //--------------------------------------------------------------------
  187. void *wlist::FirstData(){
  188.     if(Size()==0)
  189.         //----------------------------------------------------
  190.         // list empty, return null
  191.         //----------------------------------------------------
  192.         return (void *)0;
  193.     else
  194.     {
  195.         //----------------------------------------------------
  196.         // list not empty, set current to first, return the data
  197.         // contents of current node
  198.         //----------------------------------------------------
  199.         current=first;
  200.         return first->NodeData();
  201.     }
  202. }
  203. void *wlist::FirstData(void *v){
  204.     if(Size()==0)
  205.     {
  206.         //----------------------------------------------------
  207.         // list empty, append given data
  208.         //----------------------------------------------------
  209.         return AppendData(v);
  210.     }
  211.     else
  212.     {
  213.         //----------------------------------------------------
  214.         // list not empty, set current to first, replace
  215.         // data contents of first node.
  216.         //----------------------------------------------------
  217.         current=first;
  218.         return first->NodeData(v);
  219.     }
  220. }
  221.  
  222.  
  223. //--------------------------------------------------------------------
  224. // LastData - access and assign last data
  225. //--------------------------------------------------------------------
  226. void *wlist::LastData() {
  227.     if(Size()==0)
  228.         //----------------------------------------------------
  229.         // list empty, return null
  230.         //----------------------------------------------------
  231.         return (void *)0;
  232.     else
  233.     {
  234.         //----------------------------------------------------
  235.         // list not empty, set cuttent to last node, return
  236.         // last node contents
  237.         //----------------------------------------------------
  238.         current=last;
  239.         return last->NodeData();
  240.     }
  241. }
  242. void *wlist::LastData( void *v) {
  243.     if(Size()==0)
  244.     {
  245.         //----------------------------------------------------
  246.         // list empty, append given data
  247.         //----------------------------------------------------
  248.         return AppendData(v);
  249.     }
  250.     else
  251.     {
  252.         //----------------------------------------------------
  253.         // list not empty, set current to last node, replace
  254.         // data contents of last node with given data
  255.         //----------------------------------------------------
  256.         current=last;
  257.         return last->NodeData(v);
  258.     }
  259. }
  260. //--------------------------------------------------------------------
  261. // NextData - access and assign next data 
  262. //--------------------------------------------------------------------
  263. void *wlist::NextData(){
  264.     //------------------------------------------------------------
  265.     // if list is empty, return null
  266.     //------------------------------------------------------------
  267.     if(Size()==0)
  268.     {
  269.         return (void *)0;
  270.     }
  271.     //------------------------------------------------------------
  272.     // if current is last node, there is no next so return null
  273.     //------------------------------------------------------------
  274.     else if(current==last)
  275.     {
  276.         return (void *)0;
  277.     }
  278.     else
  279.     //------------------------------------------------------------
  280.     // set current to next node and return the data contents
  281.     //------------------------------------------------------------
  282.     {
  283.         current=current->NextNode();
  284.         return current->NodeData();
  285.     }
  286. }
  287. void *wlist::NextData(void *v){
  288.     //------------------------------------------------------------
  289.     // if list is empty, append node containing the given data
  290.     //------------------------------------------------------------
  291.     if(Size()==0)
  292.     {
  293.         return AppendData(v);
  294.     }
  295.     //------------------------------------------------------------
  296.     // if current is last node, append a node containing given data
  297.     //------------------------------------------------------------
  298.     else if(current==last)
  299.     {
  300.         return AppendData(v);
  301.     }
  302.     //------------------------------------------------------------
  303.     // set current to next node and replace the node data 
  304.     // contents with the given data
  305.     //------------------------------------------------------------
  306.     else
  307.     {
  308.         current=current->NextNode();
  309.         return current->NodeData(v);
  310.     }
  311. }
  312. //--------------------------------------------------------------------
  313. // PreviousData - access and assign next data 
  314. //--------------------------------------------------------------------
  315. void *wlist::PreviousData(){
  316.     //------------------------------------------------------------
  317.     // if list is empty, return null
  318.     //------------------------------------------------------------
  319.     if(Size()==0)
  320.     {
  321.         return (void *)0;
  322.     }
  323.     //------------------------------------------------------------
  324.     // if current is first node, there is no previous so return null
  325.     //------------------------------------------------------------
  326.     else if(current==first)
  327.     {
  328.         return (void *)0;
  329.     }
  330.     else
  331.     //------------------------------------------------------------
  332.     // set current to previous node and return the data contents
  333.     //------------------------------------------------------------
  334.     {
  335.         current=current->PreviousNode();
  336.         return current->NodeData();
  337.     }
  338. }
  339. void *wlist::PreviousData(void *v){
  340.     //------------------------------------------------------------
  341.     // if list is empty, append node containing the given data
  342.     //------------------------------------------------------------
  343.     if(Size()==0)
  344.     {
  345.         return AppendData(v);
  346.     }
  347.     //------------------------------------------------------------
  348.     // if current is first node, preppend a node containing given data
  349.     //------------------------------------------------------------
  350.     else if(current==first)
  351.     {
  352.         return PrependData(v);
  353.     }
  354.     //------------------------------------------------------------
  355.     // set current to previous node and replace the node data 
  356.     // contents with the given data
  357.     //------------------------------------------------------------
  358.     else
  359.     {
  360.         current=current->PreviousNode();
  361.         return current->NodeData(v);
  362.     }
  363. }
  364. //--------------------------------------------------------------------
  365. // PreInsert - insert data before current node, inserted node becomes
  366. //    current node
  367. //--------------------------------------------------------------------
  368. void *wlist::PreInsert(void *v){
  369.     if(Size()==0)
  370.         return AppendData(v);
  371.     else if(current == first)
  372.         return PrependData(v);
  373.     else
  374.     {
  375.         node *cc=current;
  376.         node *pp=current->PreviousNode();
  377.  
  378.         //---------------------------------------------------------
  379.         // create a new node and give it the data pointer
  380.         // make new node the current node
  381.         //---------------------------------------------------------
  382.         node *dd=new node;
  383.         dd->NodeData(v);
  384.  
  385.         current = dd;
  386.  
  387.         //---------------------------------------------------------
  388.         // set pointers from current node to its next and 
  389.         // previous node
  390.         //---------------------------------------------------------
  391.         current->NextNode(cc);
  392.         current->PreviousNode(pp);
  393.  
  394.         //---------------------------------------------------------
  395.         // set pointers from next and previous nodes to the
  396.         // current node
  397.         //---------------------------------------------------------
  398.         cc->PreviousNode(current);
  399.         pp->NextNode(current);
  400.  
  401.         //---------------------------------------------------------
  402.         // increment list size
  403.         //---------------------------------------------------------
  404.         ++size;
  405.  
  406.         return current->NodeData();
  407.         
  408.     }
  409. }
  410. //--------------------------------------------------------------------
  411. // PostInsert - insert data after current node, inserted node becomes
  412. //    current node
  413. //--------------------------------------------------------------------
  414. void *wlist::PostInsert(void *v){
  415.     if(Size()==0)
  416.         return AppendData(v);
  417.     else if(current == last)
  418.         return AppendData(v);
  419.     else
  420.     {
  421.         node *cc=current;
  422.         node *nn=current->NextNode();
  423.  
  424.         //---------------------------------------------------------
  425.         // create a new node and give it the data pointer
  426.         // make new node the current node
  427.         //---------------------------------------------------------
  428.         node *dd=new node;
  429.         dd->NodeData(v);
  430.         current = dd;
  431.  
  432.         //---------------------------------------------------------
  433.         // set pointers from current node to its next and 
  434.         // previous node
  435.         //---------------------------------------------------------
  436.         current->PreviousNode(cc);
  437.         current->NextNode(nn);
  438.  
  439.         //---------------------------------------------------------
  440.         // set pointers from next and previous nodes to the
  441.         // current node
  442.         //---------------------------------------------------------
  443.         cc->NextNode(current);
  444.         nn->PreviousNode(current);
  445.  
  446.         //---------------------------------------------------------
  447.         // increment list size
  448.         //---------------------------------------------------------
  449.         ++size;
  450.  
  451.         return current->NodeData();
  452.         
  453.     }
  454. }
  455. //--------------------------------------------------------------------
  456. // DeleteCurrent() - delete current node from list
  457. //--------------------------------------------------------------------
  458. void *wlist::DeleteCurrent(){
  459.     void *dd;
  460.     if(Size()==0)
  461.         return (void *)0;
  462.     else if(Size()==1)
  463.     {
  464.         dd = CurrentData();
  465.         delete current;
  466.         current = (node *)0;
  467.         first = (node *)0;
  468.         last = (node *)0;
  469.         --size;
  470.         return dd;
  471.     }
  472.     else if(current == last)
  473.     {
  474.         dd = CurrentData();
  475.         node *pp = current->PreviousNode();
  476.         delete current;
  477.         current = pp;
  478.         last = pp;
  479.         --size;
  480.         current->NextNode((node *)0);
  481.         return dd;
  482.     }
  483.     else if(current==first)
  484.     {
  485.         dd = CurrentData();
  486.         node *nn=current->NextNode();
  487.         delete current;
  488.         current = nn;
  489.         first = nn;
  490.         current->PreviousNode((node *)0);
  491.         --size;
  492.         return dd;
  493.     }
  494.     else
  495.     {
  496.         dd=CurrentData();
  497.         node *nn=current->NextNode();
  498.         node *pp=current->PreviousNode();
  499.         delete current;
  500.         current=nn;
  501.         current->PreviousNode(pp);
  502.         pp->NextNode(nn);
  503.         --size;
  504.         return dd;
  505.     }
  506. }
  507. //--------------------------------------------------------------------
  508. // DeleteAll - delete all list nodes, set size to zero - does NOT
  509. //    delete the node contents and this is a potential source
  510. //    of memory leakage
  511. //--------------------------------------------------------------------
  512. void wlist::DeleteAll(){
  513.     int i;
  514.     node *n;
  515.     current = last;
  516.     //------------------------------------------------------------
  517.     // delete each node, no action taken on the data contents
  518.     //------------------------------------------------------------
  519.     for(i=0; i<Size(); i++)
  520.     {
  521.         n=current->PreviousNode();
  522.         delete current;
  523.         current = n;
  524.     }
  525.     size=0;
  526. }
  527. //--------------------------------------------------------------------
  528. // print - print the list contents, usually for test and debug
  529. //--------------------------------------------------------------------
  530. void wlist::print (){print(stdout);}
  531.  
  532. void wlist::print(FILE *pf){
  533.     void *d;
  534.     fprintf(pf,"\tlist %s  size %d\n",Name(),Size());
  535.     fprintf(pf,"\tlist %s  node %d data %x\n",Name(),0,FirstData());
  536.     if(PrintData == 0)
  537.     {
  538.         return ;
  539.     }
  540.     PrintData(pf,FirstData());
  541.     for(int i=1; i< Size(); i++)
  542.     {
  543.         d=NextData();
  544.         fprintf(pf,"\tlist %s  node %d data %x\n",Name(),i,d);
  545.         if(d != (void *)0)
  546.             PrintData(pf,d);
  547.         else
  548.             fprintf(pf,"\t\t(null)\n");
  549.     }
  550. }
  551.  
  552. void wlist::SetPrintData(void (*f)(FILE *pf,void *d)) {
  553.     PrintData=f;
  554. }
  555. //----------------------------------------------------------------
  556. // SetCompareData - pass pointer to the data compare function to
  557. //    be stored for future reference by Sort()
  558. //----------------------------------------------------------------
  559. void wlist::SetCompareData(int (*f)(void *a, void *b)){
  560.     CompareData=f;
  561. }
  562. //----------------------------------------------------------------
  563. // Reverse - create a new list that is this list in reverse order
  564. //----------------------------------------------------------------
  565. wlist     *wlist::Reverse(){
  566.     int i;
  567.     wlist *rev = new wlist;
  568.     
  569.     for(i=0; i< Size(); i++)
  570.     {
  571.         if(i==0)
  572.             rev->NextData(LastData());
  573.         else
  574.             rev->NextData(PreviousData());
  575.     }
  576.     return rev;
  577. }
  578. //----------------------------------------------------------------
  579. // Sort - create a new list containing the data from this sorted
  580. //     in ascending order. The current node in the new list will
  581. //    be its last node and will contain the pointer to the data
  582. //    that is considered the "largest" by the compare function.
  583. //    This is a brute force implementation. If you want to efficiently
  584. //    sort large lists then the sort algorithm needs more work.
  585. //----------------------------------------------------------------
  586. wlist    *wlist::Sort(){
  587.     void    *idata;
  588.     wlist    *wl;
  589.     wlist    *xl;
  590.     int    i;
  591.  
  592.     if(CompareData == 0)
  593.     {
  594.         return (wlist *)0;
  595.     }
  596.     wl = Copy();
  597.     xl = new wlist;
  598.     for(i=0; i< Size(); i++)
  599.     {
  600.         idata=wl->Minimum();
  601.         xl->NextData(idata);
  602.         wl->DeleteCurrent();
  603.     }
  604.     delete wl;
  605.     return xl;
  606. }
  607. //----------------------------------------------------------------
  608. // ExchangePrevious() - exchange data between current and previous
  609. //    list nodes; return pointer to new current data
  610. //----------------------------------------------------------------
  611. void *wlist::ExchangePrevious(){
  612.     void    *cur;
  613.     void    *prev;
  614.  
  615.     // if list is empty or current is first node, return null
  616.     if(Size()<= 0 || current==first)
  617.     {
  618.         return (void *)0;
  619.     }
  620.     cur = CurrentData();
  621.     prev= PreviousData();
  622.     NextData(prev);
  623.     PreviousData(cur);
  624.     return NextData();
  625. }
  626.  
  627. //----------------------------------------------------------------
  628. // ExchangeNext() - exchange data between current and next list
  629. //    nodes; return pointer to new current data
  630. //----------------------------------------------------------------
  631. void *wlist::ExchangeNext(){
  632.     void    *cur;
  633.     void    *nx;
  634.  
  635.     // if list is empty or current is last node, return null
  636.     if(Size()<= 0 || current==last)
  637.     {
  638.         return (void *)0;
  639.     }
  640.     cur = CurrentData();
  641.     nx= NextData();
  642.     PreviousData(nx);
  643.     NextData(cur);
  644.     return PreviousData();
  645. }
  646. //----------------------------------------------------------------
  647. // Maximum() - return maximum data; current node is the node
  648. //    containing the maximum
  649. //----------------------------------------------------------------
  650. void *wlist::Maximum(){
  651.     //----------------------------------------------------------------
  652.     // assure that CompareData() has been assigned
  653.     //----------------------------------------------------------------
  654.     if(CompareData == 0)
  655.     {
  656.         return (void *)0;
  657.     }
  658.     //----------------------------------------------------------------
  659.     // handle the cases of zero and 1 list element
  660.     //----------------------------------------------------------------
  661.     if(Size() == 0)
  662.     {
  663.         return (void *)0;
  664.     }
  665.     if(Size()==1)
  666.     {
  667.         return FirstData();
  668.     }
  669.     int i;
  670.     void    *mx = FirstData();
  671.     void    *cur;
  672.     //----------------------------------------------------------------
  673.     // find the maximum
  674.     //----------------------------------------------------------------
  675.     for(i=0; i<(Size()-1);i++)
  676.     {
  677.         cur=NextData();
  678.         if(CompareData(cur,mx) > 0)
  679.             mx=cur;
  680.     }
  681.     //----------------------------------------------------------------
  682.     // set the current node to that containing the maximum
  683.     //----------------------------------------------------------------
  684.     for(i=0; i< Size(); i++)
  685.     {
  686.         if(i==0)
  687.             cur=FirstData();
  688.         else
  689.             cur=NextData();
  690.         if(CompareData(cur,mx)==0)
  691.             break;
  692.     }
  693.     return mx;
  694. }
  695. //----------------------------------------------------------------
  696. // Minimum() - return minimum data; current node is the node
  697. //    containing the minimum
  698. //----------------------------------------------------------------
  699. void *wlist::Minimum(){
  700.     //----------------------------------------------------------------
  701.     // assure that CompareData() has been assigned
  702.     //----------------------------------------------------------------
  703.     if(CompareData == 0)
  704.     {
  705.         return (void *)0;
  706.     }
  707.     //----------------------------------------------------------------
  708.     // handle the cases of zero and 1 list element
  709.     //----------------------------------------------------------------
  710.     if(Size() == 0)
  711.     {
  712.         return (void *)0;
  713.     }
  714.     if(Size()==1)
  715.     {
  716.         return FirstData();
  717.     }
  718.     int i;
  719.     void    *mx = FirstData();
  720.     void    *cur = (void *)0;
  721.     //----------------------------------------------------------------
  722.     // find the minimum
  723.     //----------------------------------------------------------------
  724.     for(i=0; i<(Size()-1);i++)
  725.     {
  726.         cur=NextData();
  727.         if(CompareData(cur,mx) < 0)
  728.             mx=cur;
  729.     }
  730.     //----------------------------------------------------------------
  731.     // set the current node to that containing the minimum
  732.     //----------------------------------------------------------------
  733.     for(i=0; i< Size(); i++)
  734.     {
  735.         if(i==0)
  736.             cur=FirstData();
  737.         else
  738.             cur=NextData();
  739.         if(CompareData(cur,mx)==0)
  740.             break;
  741.     }
  742.     return mx;
  743. }
  744. //----------------------------------------------------------------
  745. // Copy - create a copy of this; a new wlist is created.  Each
  746. //    node of the new list contains the same data pointer as
  747. //    the corresponding node of this. No attempt is made to 
  748. //    copy the contents of the data structure pointed to
  749. //    at each node. (This is a level 1 copy.)
  750. //----------------------------------------------------------------
  751. wlist    *wlist::Copy(){
  752.     wlist *wl = new wlist;
  753.     int    i;
  754.     for(i=0; i<Size(); i++)
  755.     {
  756.         if(i==0)
  757.         {
  758.             wl->FirstData(FirstData());
  759.         }
  760.         else
  761.         {
  762.             wl->NextData(NextData());
  763.         }
  764.     }
  765.     wl->PrintData=PrintData;
  766.     wl->CompareData=CompareData;
  767.     return wl;
  768. }
  769.     
  770.